/****************************************************************
 * Homework 7 'Scheduler' class implementation file
 * Author: Duncan Buell
 * Modified by: Andrew Shore, Wes Ring, Colin Edwards, JC Anderson
 *              Donald Lemaster, Byron Alleman, Brett Shoffner
 * Date last modified: 20 April 2010
 *
 * This class manages a priority queue of process blocks for
 * simulating process management in an operating system. It is
 * slightly more complex than Homework 5 and 6 since process are
 * loaded into a pending queue first and then put it the ready
 * queue when they are ready to start. Also new process are 
 * randomly generated at each time step and added to the pending
 * queue. Other changes include intializing the pending queue 
 * with random processes instead of processes from an input file
 * and computing mean and standard deviations in the runSimulation
 * function.
 *
 *
**/

#include "Scheduler.h"

static const char TAG[] = "Scheduler: ";

/****************************************************************
 * Constructor.
**/
Scheduler::Scheduler()
{
}

/****************************************************************
 * Destructor.
**/
Scheduler::~Scheduler()
{
}


/*******************************************************************************
 * Function to create a process using the given parameters and add it to the
 * pending priority queue.
 * Author: Andrew Shore, Wes Ring, JC Anderson, Colin Edwards
 * Date Last Modified: 1 April 2010
 *
 * This function creates a new process, sets the class variables of that
 * process by passing the parameters to the mutator functions and then uses
 * the STL priority queue function push() to add it to the pending queue.
 * No error checking is done in this function, the parameters are assumed to
 * be correct when passed in by the main function.
 *
 * Parameters:
 *   long pid - used to set process id
 *   long startTime - used to set start time
 *   long execTime - used to set execution time
 *
 * Output: none
 *
 * Returns: none
*******************************************************************************/
void Scheduler::addPending(long pid, long startTime, long execTime){
  Process newProcess;
  newProcess.setPid(pid);
  newProcess.setStartTime(startTime);
  newProcess.setExecTime(execTime);

  thePendingQ.push(newProcess);

}//void Scheduler::addPending(long pid, long startTime, long execTime)

/*******************************************************************************
 * Function to check if both priority queues are empty.
 * Author: Andrew Shore, Wes Ring, JC Anderson, Colin Edwards
 * Date Last Modified: 1 April 2010
 *
 * Simply calls the STL priority queue function empty() to check if both the
 * 'theReadyQ' and the 'thePendingQ' are empty.
 *
 *
 * Parameters: none
 *
 * Output: none
 *
 * Returns: True if both the pending and ready queue are empty, false otherwise
*******************************************************************************/
bool Scheduler::empty(){
  if( theReadyQ.empty() && thePendingQ.empty() ){
    return true;
  }else{
    return false;
  }
}//bool Scheduler::empty()

/*******************************************************************************
 * Function to 'pop' off(remove) top element in the ready priority queue.
 * Author: Andrew Shore, Wes Ring, JC Anderson, Colin Edwards
 * Date Last Modified: 1 April 2010
 *
 * Function pops off the top element of the queue(the element with the smallest
 * finish time) provided the priority queue is non-empty.
 *
 * Parameters: none
 *
 * Output: none
 *
 * Returns: none
*******************************************************************************/
void Scheduler::readyPop(){
  if( !theReadyQ.empty() ){
    theReadyQ.pop();
  }
}//void Scheduler::readyPop()

/*******************************************************************************
 * Function to 'pop' off(remove) top element in the pending queue
 * Authors: Andrew Shore, JC Anderson, Wes Ring, Colin Edwards
 * Date Last Modified: 1 April 2010
 *
 * Function pops off the top element of the pending queue(the element with the
 * smallest start time) provided the priority queue is non-empty.
 *
 * Parameters: none
 *
 * Output: none
 *
 * Returns: none
*******************************************************************************/
void Scheduler::pendingPop(){
  if( !thePendingQ.empty() ){
    thePendingQ.pop();
  }
}//void Scheduler::pendingPop()

/*******************************************************************************
 * Function to look at the top process of the ready queue but not remove it
 * Author: Andrew Shore, Wes Ring, JC Anderson, Colin Edwards
 * Date Last Modified: 1 April 2010
 *
 * If the priority queue is non-empty it returns the top process, otherwise
 * it returns an unitialized proccess.
 *
 * Parameters: none
 *
 * Output: none
 *
 * Returns: A process with the smallest finish time
*******************************************************************************/
Process Scheduler::readyTop(){
  Process temp;
  if( theReadyQ.empty() ){
    return temp;
  }else{
    return theReadyQ.top();
  }
}//Process Scheduler::readyTop()

/*******************************************************************************
 * Function to look at the top process of the pending queue but not remove it
 * Authors: Andrew Shore, JC Anderson, Wes Ring, Colin Edwards
 * Date Last Modified: 1 April 2010
 *
 * If the priority queue is non-empty it returns the top process, otherwise it
 * returns an unitialized process.
 *
 * Parameters: none
 *
 * Output: none
 *
 * Returns: A process with the smallest start time
*******************************************************************************/
Process Scheduler::pendingTop(){
  Process temp;
  if( thePendingQ.empty() ){
    return temp;
  }else{
    return thePendingQ.top();
  }
}//Process Scheduler::pendingTop()

/*******************************************************************************
 * Function to 'dump' the pending queue and assign it to a string
 * Authors: Andrew Shore, JC Anderson, Wes Ring, Colin Edwards
 * Date Last Modified: 1 April 2010
 *
 * This function first creates a copy of the pending queue so we do not destroy
 * the orginal queue. Then the top element is added to the string using the
 * toString function of the process class. The element is then popped off the
 * queue. The function does this until there are no more elements in the queue
 * and then returns a string that is an ordered list(by startTime) of processes.
 *
 * Parameters: none
 *
 * Output: log of what occurs
 *
 * Returns: string version of the pending queue
 */
string Scheduler::toStringDumpPendingQ(){
cout << TAG << " enter toStringDumpPendingQ\n";

  string s = "";
  Process temp;
  priority_queue<Process, vector<Process>, ComparisonStart>
                                       tempPQ = thePendingQ;

  cout << TAG << " pending queue:\n";
  if ( tempPQ.empty() ){
    s += "empty";
  }else{
    while( !tempPQ.empty() ){
      temp = tempPQ.top();
      s += temp.toString() + "\n";
      tempPQ.pop();
    }//while( !tempPQ.empty() )
  }

  s += Utils::Format(TAG);
  s += " leaving toStringDumpPendingQ\n";
  return s;

}//string Scheduler::toStringDumpPendingQ()

/*******************************************************************************
 * Function to 'dump' the ready queue and assign it to a string
 * Authors: Andrew Shore, JC Anderson, Wes Ring, Colin Edwards
 * Date Last Modified: 1 April 2010
 *
 * Function first creates a copy of the ready queue so we don't destroy the
 * original queue. If the queue is empty the string "empty" is returned. If it
 * is not empty the top element of the queue is assigned to a string using the
 * toString function of the process class then the element is popped off. This
 * is repeated until the queue contains no elements. As it is in the current
 * implementation this function is only called when the theReadyQ is empty,
 * the normal non-empty dump is included for debugging purposes.
 *
 * Parameters: none
 *
 * Output: log of what occurs
 *
 * Returns: a string version of the ready queue
 */
string Scheduler::toStringDumpReadyQ(){
  cout << TAG << "enter toStringDumpReadyQ\n";

  cout << TAG << "ready queue:\n";

  priority_queue<Process, vector<Process>, ComparisonFinish>
                                       tempPQ = theReadyQ;
  string s;
  Process temp;

  if( tempPQ.empty() ){
    cout << TAG << "empty queue\n";

  }else{
    while( !tempPQ.empty() ){
      temp = tempPQ.top();
      s += temp.toString() + "\n";
      tempPQ.pop();
    }//while( !tempPQ.empty() )

  }

  cout << TAG << "leave toStringDumpReadyQ\n";

  return s;
}//string Scheduler::toStringDumpReadyQ()

/*****************************************************************************
 * Function to put the processes in the input file into the pending queue
 * Authors: Andrew Shore, JC Anderson, Wes Ring, Colin Edwards
 * Date Last Modified: 1 April 2010
 *
 * This function reads in the pid, startTime, execTime from the input file and
 * then adds the procces to the queue using the function addPending. No error
 * checking is done in this function the file is assumed to be formatted
 * correctly and contains correct data.
 *
 * Parameters:
 *   inStream - file containing the list of process to be simulated, formatted
 *              'pid  startTime  execTime'
 *
 * Output: none
 *
 * Returns: none
 *
 * Note: function no longer used, replaced by intializePendingQ
 */
/*
void Scheduler::loadPendingQ(ifstream& inStream){
  long pid;
  long startTime;
  long execTime;
  while( inStream >> pid ){
    inStream >> startTime;
    inStream >> execTime;
    addPending(pid, startTime, execTime);
  }//while( inStream >> pid)


}//void Scheduler::loadPendingQ(ifstream& inStream)
*/

/*******************************************************************************
 * Initializes a pending queue with randomly generated processes.
 * Authors: Andrew Shore, Brett Shofner, Donald Lemaster, Byron Alleman
 * Date Last Modified: 20 April 2010
 *
 * Parameters:
 *   ifstream& - stream for the file containing the maximum start time,
 *               maximum number of items initialized with a starting 
 *               time, and the maximum execution time per process.
 *
 * This function gets the maximum start time of the processes, the 
 * maximum number of processes with the same starting time, and 
 * the maximum execution time of the processes for the initial pending 
 * queue.  The function then adds random processes to the initial 
 * pending queue with the processes organized by start time. Note: The variable
 * pidCounter is a class variable that is incremented every time a process is  
 * added anywhere in the program as to avoid having multiple process with the 
 * same pid. maxExec time is also a class variable since it is used in the 
 * runSimulation function as well.
 *
 * Output: none
 *
 * Returns: none
*******************************************************************************/
void Scheduler::intializePendingQ(ifstream& inStream){
  long startInit;
  long maxInit;
  long randGenerate;
  long randExec;

  pidCounter = 1;
  inStream >> startInit;
  inStream >> maxInit;
  inStream >> maxExecTime;

  srand(0);

  for( int i = 1; i <= startInit ; i++){
    randGenerate = (rand() % (maxInit + 1));
    for( int j = 0; j < randGenerate; j++){
      randExec = (rand() % maxExecTime) + 1;

      addPending( pidCounter, i , randExec);

      pidCounter++;
    }
  }

}//void Scheduler::intializePendingQ(ifstream& inStream)

/*******************************************************************************
 * Function runs a simulation of processes much like the main class did
 * in Assignment 5 and 6 only more complex.
 * 
 * Authors: Andrew Shore, JC Anderson, Wes Ring, Colin Edwards
 * Modified by: Brett Shofner, Donald Lemaster, Byron Alleman
 * Date Last Modified: 20 April 2010
 *
 * Parameters:
 *   ifstream& - stream for the file containing the maximum start time, maximum
 *               number of new generated processes per time step, the maximum
 *               execution time of each process, and the frequency at which
 *               to display mean and standard deviation information.
 * 
 * This function first initializes the pending queue with the 
 * initializePendingQ function.  Then the function gets from the input 
 * stream the maximum number of time steps to run the simulation for, 
 * the maximum number of new generated processes per time step, the 
 * maximum time difference between the current time step and new 
 * generated process start times, and the frequency at which to print 
 * the mean and standard deviation information.  If the input file has
 * -1 as the maximum number of time steps the simulation is set to run
 * indefinitely by setting maxTimeStep equal to numeric_limits<long>::max().
 * 
 * Then the simulation is run until maxTimeStep is reached.  During each
 * time step, the function adds processes from pendingQ to readyQ if 
 * the process's start time is equal to the current time step.  It then
 * removes any processes from the readyQ with a finish time equal to the
 * current time step.  Then the function generates anywhere from 0 to 
 * maxSim new processes.  Finally the function calculates the mean and
 * standard deviation of finishing times, processes moved, size of the 
 * pending queue, and the size of the ready queue and prints this data
 * if the timestep modded with the frequency is equal to 0.
 * 
 * Output: log of what occurs
 *
 * Returns: none
*******************************************************************************/
void Scheduler::runSimulation(ifstream& inStream){

  long currentTimeStep = 0;
  Process tempProc;
  //Process finishProc;
  //variables read from input file
  long maxTimeStep;
  long maxSim;
  long startSim;
  int frequency;
  //random variables for generating new processes
  long randGenerate;
  long randStart;
  long randExec;
  //variables for computing mean and std dev. of processes finishing
  int finishSum = 0;
  int finishCount = 0;
  double finishMean = 0;
  double finishM2 = 0;
  double finishDelta = 0;
  //variables for computing mean and std. dev. of processes moved
  int moveSum = 0;
  int moveCount = 0;
  double moveMean = 0;
  double moveM2 = 0;
  double moveDelta = 0;
  //variables for computing mean and std. dev. of size of pending queue
  int pendingSum = 0;
  int pendingCount = 0;
  double pendingMean = 0;
  double pendingM2 = 0;
  double pendingDelta = 0;
  //variables for computing mean and std. dev. of size of ready queue
  int readySum = 0;
  int readyCount = 0;
  double readyMean = 0;
  double readyM2 = 0;
  double readyDelta = 0;
  
  srand(0);
  
  cout << TAG << "entering runSimulation function\n";

  intializePendingQ(inStream);

  inStream >> maxTimeStep;
  inStream >> maxSim;
  inStream >> startSim;
  inStream >> frequency;

 
 
	
  if( maxTimeStep == -1){
    maxTimeStep = numeric_limits<long>::max();
  }

  cout << TAG << "Simulation running for " << maxTimeStep << " timesteps " <<
              "and printing mean and standard deviation every " << frequency << 
              " timesteps.\n";

  cout << toStringDumpPendingQ() << endl;
  cout << toStringDumpReadyQ() << endl;

  while( currentTimeStep <= maxTimeStep){

    /*Resets count variables to allow a count for each individual
      timestep and not a total sum
    */
    finishCount = 0;
    moveCount = 0;
    pendingCount = 0;
    readyCount = 0;

    if( empty() ){
      cout << TAG << "no more processes, ending execution\n";
      break;
    }

    /* Adds processes to ready queue when ready to start
     */
    cout << TAG << "adding at time  " << currentTimeStep << endl;
    if(  pendingTop().getStartTime() == currentTimeStep){

      while( pendingTop().getStartTime() == currentTimeStep ){
        tempProc = pendingTop();
        cout << "     "  <<  "adding     " << tempProc.toString() << endl;
        theReadyQ.push(tempProc);
        pendingPop();
        moveCount++;
      }//while( pendingTop().getStartTime() == currentTimeStep)
    }else if( thePendingQ.empty() ){
      cout << "     pending queue is empty\n";
    }
    else{
      cout << "     no processes added at time " << currentTimeStep << endl;
    }

    /* Removes process from ready queue when finished
     */
    cout << TAG << "finishing at time " << currentTimeStep << endl;
    if(  readyTop().getFinishTime() == currentTimeStep){

      while( readyTop().getFinishTime() == currentTimeStep ){
        tempProc = readyTop();
        cout << "     " << "finishing  " << tempProc.toString() << endl;
        readyPop();
        finishCount++;

      }//while( readyTop().getFinishTime() == currentTimeStep)
    }else{
      cout << TAG << "no processes finishing at time "
           << currentTimeStep << endl;
    }
    if( theReadyQ.empty() ){
      cout << "     ready queue is empty\n";
    }

    /* Generates a random number of processes and adds them to the pendingQ
     */
    randGenerate = (rand() % (maxSim + 1));
    cout << "Generating " << randGenerate << " new processes at time step " <<
      currentTimeStep << endl;
    for(int i = 0; i < randGenerate; i++){
      randStart = (rand() % startSim) + 1;
      randExec = (rand() % maxExecTime) + 1;

      tempProc.setPid(pidCounter);
      tempProc.setStartTime(randStart + currentTimeStep);
      tempProc.setExecTime(randExec);

      cout << "     " << tempProc.toString() << endl;
      addPending( pidCounter, randStart + currentTimeStep, randExec);
      pidCounter++;

    }

    pendingCount = thePendingQ.size();
    readyCount = theReadyQ.size();

    //computations for mean
    finishSum += finishCount;
    moveSum += moveCount;
    pendingSum += pendingCount;
    readySum += readyCount;

    //compuations for standard deviation
    if(currentTimeStep != 0){
     
      finishDelta = finishCount - finishMean;
      finishMean = finishMean + (finishDelta / 
                   static_cast<double>(currentTimeStep + 1));
      finishM2 = finishM2 + finishDelta * 
                 (static_cast<double>(finishCount) - finishMean);

      moveDelta = moveCount - moveMean;
      moveMean = moveMean + (moveDelta / 
                 static_cast<double>(currentTimeStep + 1));
      moveM2 = moveM2 + moveDelta * (static_cast<double>(moveCount) - moveMean);

      pendingDelta = pendingCount - pendingMean;
      pendingMean = pendingMean + (pendingDelta / 
                    static_cast<double>(currentTimeStep + 1));
      pendingM2 = pendingM2 + pendingDelta * 
                  (static_cast<double>(pendingCount) - pendingMean);

      readyDelta = readyCount - readyMean;
      readyMean = readyMean + (readyDelta / 
                  static_cast<double>(currentTimeStep + 1));
      readyM2 = readyM2 + readyDelta * 
                (static_cast<double>(readyCount) - readyMean);

    }

    //computes standard deviation and mean every N time steps
    if(currentTimeStep == 0){
      cout  << TAG << "The mean number of proccess finishing at any " <<
                      "given time step is " <<
                      (static_cast<double>(finishSum) / 
                      static_cast<double>(ONE)) << endl; 
   
      cout << TAG << "The standard deviation for the number of processes " <<
                     "finishing is " << sqrt( finishM2 / 
                      static_cast<double>(ONE)) << endl;

      cout << TAG << "The mean number of process moved at any given time " <<
                     "step is " << (static_cast<double>(moveSum) / 
                     static_cast<double>(ONE)) << endl;

      cout << TAG << "The standard deviation for the number of processes " <<
                     "moved is " << sqrt(moveM2 / 
                     static_cast<double>(ONE)) << endl;

      cout << TAG << "The mean of the size of the pending queue at any " << 
                   "given time step is " << (static_cast<double>(pendingSum) / 
                   static_cast<double>(ONE)) << endl;
      
      cout << TAG << "The standard deviation of the size of the pending " << 
                     "queue at any given time step is " << sqrt(pendingM2 / 
                     static_cast<double>(ONE)) << endl;

      cout << TAG << "The mean of the size of the ready queue at any given " <<
		     "time step is " << (static_cast<double>(readySum) / 
		      static_cast<double>(ONE)) << endl;
      
      cout << TAG << "The standard deviation of the size of the ready " <<
	             "queue at any given time step is " << sqrt(readyM2 / 
	             static_cast<double>(ONE)) << endl;


    }else if( currentTimeStep % frequency == 0){
      
      cout << TAG << "The mean number of proccess finishing at any " <<
                     "given time step is " << 
                     (static_cast<double>(finishSum) / 
                     static_cast<double>(currentTimeStep)) << endl;

     
      cout << TAG << "The standard deviation for the number of processes " <<
                     "finishing is " << sqrt( finishM2 / 
                     static_cast<double>(currentTimeStep)) << endl;

      cout << TAG << "The mean number of process moved at any given time " <<
                     "step is " << (static_cast<double>(moveSum) / 
                     static_cast<double>(currentTimeStep)) << endl;
      
      cout << TAG << "The standard deviation for the number of processes " <<
                     "moved is " << sqrt(moveM2 / 
                     static_cast<double>(currentTimeStep)) << endl;

      cout << TAG << "The mean of the size of the pending queue at any " << 
                   "given time step is " << (static_cast<double>(pendingSum) / 
                   static_cast<double>(currentTimeStep)) << endl;
      
      cout << TAG << "The standard deviation of the size of the pending " << 
                     "queue at any given time step is " << sqrt(pendingM2 / 
                      static_cast<double>(currentTimeStep)) << endl;

      cout << TAG << "The mean of the size of the ready queue at any given " <<
		     "time step is " << (static_cast<double>(readySum) / 
		     static_cast<double>(currentTimeStep)) << endl;
      
      cout << TAG << "The standard deviation of the size of the ready " <<
	             "queue at any given time step is " << sqrt(readyM2 / 
	             static_cast<double>(currentTimeStep)) << endl;
    }

    cout << endl;
    currentTimeStep++;

  }//while( currentTimeStep != maxTimeStep)
  cout << TAG << "leaving runSimulation function\n";
}//void Scheduler::runSimulation(ifstream& inStream, long maxTimeStep)



